package a4_queue.impl;

import a4_queue.Queue;
import java.util.NoSuchElementException;

/**
 * 基于数组实现的环形队列
 * @param <E>
 */
public class LoopQueue<E> implements Queue<E> {

    //定义存储元素的数组
    private Object[] data;
    //指向队首元素
    private int head;
    //指向队尾元素的下一位
    private int tail;
    //当前队列中有效元素的个数
    private int size;

    //构造方法
    public LoopQueue(int n) {
        //在循环队列中要浪费一个空间不能存储元素
        this.data = new Object[n + 1];
    }

    @Override
    public void offer(E val) {
        if(isFull()){
            throw new ArrayIndexOutOfBoundsException("queue is full! cannot offer!");
        }
        //队尾新增元素
        data[tail] = val;
        //tail的指向后移一位
        tail = (tail + 1) % data.length;
        size ++;
    }

    @Override
    public E poll() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot poll!");
        }
        E val = (E) data[head];
        head = (head + 1) % data.length;
        size --;
        return val;
    }

    @Override
    public E peek() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot peek!");
        }
        return (E) data[head];
    }

    @Override
    public boolean isEmpty() {
        //如果为空，head和tail在同一位置
        return head == tail;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Front [");
        for(int i=head; i<tail; i=(i+1)%data.length){
            sb.append(data[i]);
            if((i+1)% data.length != tail){
                sb.append(", ");
            }
        }
        sb.append("] Tail");
        return sb.toString();
    }

    //判断队列是否已满
    public boolean isFull() {
        //如果已满，tail的下一位就是head
        return (tail+1)% data.length == head;
    }
}
